package 数组算法;

public class islandPerimeter463 {
    /**
     * 对于一个陆地格子的每条边，它被算作岛屿的周长当且仅当这条边为网格的边界或者相邻的另一个格子为水域。
     * 因此，我们可以遍历每个陆地格子，看其四个方向是否为边界或者水域，
     * 如果是，将这条边的贡献（即 11）加入答案 \textit{ans}ans 中即可。
     *
     * @param grid
     * @return
     */

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public int islandPerimeter(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果是陆地
                if (grid[i][j] == 1) {
                    int sum = 0;
                    // 查看四周是否为为水
                    for (int k = 0; k < 4; k++) {
                        int nx = dx[k] + i;
                        int ny = dy[k] + j;
                        // 如果有超过边界 或者的是等于水的话，那就是表示这个是是是一个有效的边
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == 0) {
                            sum += 1;
                        }
                    }
                    ans += sum;
                }
            }
        }
        return ans;
    }

    public int islandPerimeterV2(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    ans += dfs(grid, i, j);
                }
            }
        }
        return ans;
    }

    private int dfs(int[][] grid, int x, int y) {
        // 表示出界或者是的表示有水是1的时候就返回1
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) {
            return 1;
        }
        if (grid[x][y] == 2) {
            return 0;
        }
        grid[x][y] = 2;
        int res = 0;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            res += dfs(grid, tx, ty);
        }
        return res;
    }
}
